class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        res = 1
        for i in range(1, n // 2 + 1):
            mid_num = 1
            for j in range(1, i + 1):
                mid_num *= (n - i - j + 1)
                mid_num /= j
            res += mid_num
        return int(res)


a = Solution()
print(a.climbStairs(3))
print(a.climbStairs(4))
print(a.climbStairs(5))
print(a.climbStairs(6))
print(a.climbStairs(7))